package com.wp.data_structure.code;


import org.apache.commons.lang3.StringUtils;

import java.util.Arrays;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author wangpeng
 * @description ******
 * @date 2021/11/24 14:32
 */
public class MyTest {
    public static void main(String[] args) {

        String[][][] qwe = new String[3][2][5];
        System.out.println(qwe.length);

        String s = "abcabcabc";
        //非贪婪模式
        String patternString = "a(.*?)c";
        //贪婪模式
        String patternString1 = "a(.*)c";
        Pattern pattern = Pattern.compile(patternString);
        Pattern pattern1 = Pattern.compile(patternString1);
        Matcher m = pattern.matcher(s);
        Matcher m1 = pattern1.matcher(s);

//        System.out.println(m.find()? m.group(1):"");
        System.out.println(m.group());
        System.out.println(m.group(1));
        System.out.println(m.group(2));
        System.out.println(m.group(3));
//        System.out.println(m1.find()? m1.group(1):"");

//        String wp = "wangpeng";
//        byte[] bytes = wp.getBytes();
//        for (byte e :
//                bytes) {
//            System.out.println((char) e);
//        }
//        String ss = new String(bytes,StandardCharsets.UTF_8);
//
//        System.out.println(ss);

//        String mainString = "wangpeng";
//        String pattern = "eng";
//        System.out.println(StringMatch.getIndexBetter(mainString,pattern));

        ReturnResult result = BinaryNode.getByString("ABC###E#G##",0);

        System.out.println(BinaryNode.traverse(result.getBinaryNode()));
    }
}

class ReturnResult {
    private int index;
    private BinaryNode binaryNode;

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public BinaryNode getBinaryNode() {
        return binaryNode;
    }

    public void setBinaryNode(BinaryNode binaryNode) {
        this.binaryNode = binaryNode;
    }
}


class BinaryNode {

    private static final String splitString = "#";

    private String data;
    private BinaryNode leftSon;
    private BinaryNode rightSon;

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public BinaryNode getLeftSon() {
        return leftSon;
    }

    public void setLeftSon(BinaryNode leftSon) {
        this.leftSon = leftSon;
    }

    public BinaryNode getRightSon() {
        return rightSon;
    }

    public void setRightSon(BinaryNode rightSon) {
        this.rightSon = rightSon;
    }


    public static ReturnResult getByString (String innitString,int index) {
        ReturnResult result = new ReturnResult();
        if(index >= innitString.length()){
            return result;
        }
        BinaryNode binaryNode = new BinaryNode();
        String str = innitString.substring(index,index+1);
        result.setIndex(++index);
        if(!str.equals(splitString)){
            binaryNode.setData(str);
            ReturnResult result1 = getByString(innitString,index);
            index = result1.getIndex();
            binaryNode.setLeftSon(result1.getBinaryNode());
            ReturnResult result2 = getByString(innitString,index);
            binaryNode.setRightSon(result2.getBinaryNode());
            result.setIndex(result2.getIndex());
            result.setBinaryNode(binaryNode);
        }
        return result;
    }


    public static String traverse (BinaryNode binaryNode) {
        if(binaryNode==null){
            return "";
        }
        return binaryNode.getData()+traverse(binaryNode.getLeftSon())+traverse(binaryNode.getRightSon());
    }
}





class StringMatch {

    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 =  "ABCDABCDABDE";
        String str3 = "BBC";
        String str4 = "ABCDABEAB";
        String pattern = "ABCDABD";
        System.out.println(kmpCopy(str1, pattern));//  15  终止时i=15
        System.out.println(kmpCopy(str2, pattern));//  4    终止时i=4
        System.out.println(kmpCopy(str3, pattern));// -1    终止时i=0
        System.out.println(kmpCopy(str4, pattern));// -1    终止时i=6
    }

    public static int kmpCopy(String S, String P){
        int[] next = getNext(P);// 求next数组
        int matchSize = 0;// 已经匹匹配的长度
        int i = 0, j = 0;
        while (i < S.length() && S.length() - i >= P.length() - j) {// 注意终止条件
            if (S.charAt(i) == P.charAt(j) && j < P.length()) {
                matchSize++;//已经匹配的长度
                i++;
                j++;
            }else{
                if(j==0){
                    i++;// 移动主串
                    matchSize=0;// 已匹配长度清零
                }else{
                    // 保持主串指针不动，移动模式串到合适位置
                    matchSize=next[j-1];// 重置已匹配的长度
                    j = next[j-1];// 注意这里要取Pj-1 的最长前缀长度，因为Pj是不匹配字符
                }
            }
            if(matchSize == P.length()){// 已匹配的长度等于模式串的长度了
                return i-P.length();
            }
        }
        System.out.println("i = " + i);
        return -1;
    }

    private static int[] getNext(String P) {
        //生成next数组
        int[]next = new int[P.length()];
        int j = 1;
        int k = 0;
        while (j < P.length() && k >= 0) {
            if (P.charAt(j) == P.charAt(k)) {
                next[j] = ++k;
                j++;// 找到了最大长度的前后缀公共元素
            } else {
                if (k >= 1) {
                    k = next[k - 1];// 取前缀的最大前缀
                } else {
                    // 没找到前缀后缀的公共元素最大长度
                    k=0;
                    j++;
                }
            }
        }
        System.out.println(Arrays.toString(next));
        return next;
    }


    public static int getIndexMuchBetter(String mainString ,String pattern) {
        if(!isValid(mainString,pattern)){
            return -1;
        }



        return -1;

    }

    public static int getIndexBetter (String mainString ,String pattern) {
        if(!isValid(mainString,pattern)){
            return -1;
        }

        int i = 0;
        int j = 0;

        byte[] bytesMain = mainString.getBytes();
        byte[] bytesPattern = pattern.getBytes();
        while (i < bytesMain.length && j < bytesPattern.length) {
            if(bytesMain[i]==bytesPattern[j]){
                i++;
                j++;
            }else{
                i = i-j+1;
                j = 0;
            }

            if(j == bytesPattern.length){
                return i-j;
            }
        }

        return -1;
    }

    private static boolean isValid (String mainString, String pattern){
        boolean result = !StringUtils.isEmpty(mainString) && !StringUtils.isEmpty(pattern);
        if(mainString.length()<pattern.length()){
            result = false;
        }
        return result;
    }

    public static int getIndex (String mainString, String pattern) {
        if(!isValid(mainString,pattern)){
            return -1;
        }

        byte[] bytesMain = mainString.getBytes();
        byte[] bytesPattern = pattern.getBytes();
        int index = -1;
        loop1:
        for (int i = 1; i <= bytesMain.length; i++) {
            for (int j = 1; j <=bytesPattern.length; j++) {
                byte bytePattern = bytesPattern[j-1];
                if(bytePattern!=bytesMain[i+j-2]){
                    continue loop1;
                }
                if (j == bytesPattern.length) {
                    index = i;
                }
            }

        }
        return index;
    }

}
